POJ 3660 牛的排名 （Floyd 传递闭包）

题意： 

有n头牛， 给你m对关系（a, b）表示牛a能打败牛b， 求在给出的这些关系下， 能确定多少牛的排名。

思路：这题的难点就是，牛到达怎么样的状态，才能说他的排名是确定的。。。

仔细想想就是比牛强的人 + 比牛弱的人 == n-1  （自己不要考虑进去）

然后嘛解决此类办法是  传递闭包了！！！！

分析：

在这呢先说一下关系闭包：  

关系闭包有三种： 自反闭包（r）， 对称闭包（s）， 传递闭包（t)。

先画出 R 的关系图，再画出 r(R), s(R), t(R) 的关系图。

我们今天用的是传递闭包。   仅作为个人理解 传递闭包： 关系之间具有传递性（例如a> b, b> c, 那么a> c）， 在那些已给出的关系基础上， 通过传递性， 把所有可能的关系都找出来。  如上图。

这里需要先求一下所有牛之间的传递闭包， 那么我们这题与传递闭包又有什么关系呢。 下面将慢慢解答。 

如果一头牛被x头牛打败，并且可以打败y头牛，如果x+y=n-1，则我们容易知道这头牛的排名就被确定了，所以我们只要将任一头牛，可以打败其他的牛的个数x， 和能打败该牛的牛的个数y求出来，在遍历所有牛判断一下是否满足x+y=n-1，就知道这个牛的排名是否能确定了（而传递闭包，正好将所有能得出关系都求出来了）， 再将满足这个条件的牛数目加起来就是所求解。 x可以看成是入度， y是出度。

在floyd-warshall（不了解该算法的点这里）求每对顶点间的最短路径算法中，可以通过O(v^3)的方法求出图的传递闭包。可以位每条边赋以权值1,然后运行Floyd-Wareshall。如果从  i  到  j  存在一条路径，则d(i,j)>n>>m; while(m--) { cin>>u>>v; dp[u][v]=1; } for(k=1;k